a. Field of the Invention
The present invention concerns the management of computer memory systems, and in particular, systems with cache memory.
b. Related Art
.sctn.1. CACHE BACKGROUND
A cache memory device is a small, fast memory which should contain the most frequently accessed data (or "words") from a larger, slower memory.
Disk drive based memory affords large amounts of storage capacity at a relatively low cost. Unfortunately, access to disk drive memory is slow relative to the processing speed of modern microprocessors. A cost effective, prior art solution to this problem provides a cache memory between the processor and the disk memory system. To reiterate, the storage capacity of the cache memory is relatively small, but can be used to provide high speed access to the data.
The operating principle of the disk cache memory is the same as that of a central processing unit (or CPU) cache. More specifically, the first time an instruction or data location is addressed, it must be accessed from the lower speed disk memory. Subsequent accesses to the same instruction or data are done via the faster cache memory, thereby minimizing access time and enhancing overall system performance. However, since the storage capacity of the cache is limited, and typically is much smaller than the storage capacity of the disk storage, the cache often is filled and some of its contents must be changed (e.g., with a replacement algorithm) as new instructions or data are accessed from the disk storage.
The cache is managed, in various ways, such that it stores the instruction or data most likely to be needed at a given time. When the cache is accessed and contains the requested data, a cache "hit" occurs. Otherwise, if the cache does not contain the requested data, a cache "miss" occurs. Thus, the cache contents are typically managed in an attempt to maximize the cache hit-to-miss ratio.
FIG. 1 illustrates a high level block diagram of a conventional disk array controller 104 arranged between a host computer 102 and a disk storage array 106. The host computer 102 may include a processor 114, a memory 116, and an input/output interface 118 sharing a bus 112. The memory 116 may include a program storage section for storing program instructions for execution by the processor 114. The input/output interface 118 may use a standard communications protocol, such as the Small Computer System Interface (or "SCSI") protocol for example, to facilitate communication with peripheral devices. The disk array 106 may include an array of magnetic or optical disks 132 for example.
The disk array controller 104 includes an I/O management controller 124, a cache 126, and input/output interface(s) 128, which share a bus 122. The I/O management controller 124, which may be an application specific integrated circuit (or "ASIC") or a processor executing stored instructions for example, controls reading from and writing to the cache 126 and the disk array 106. The input/output interface(s) 128 may use the SCSI protocol to facilitate communication between it, the host computer 102, and the disk array 106.
The conventional system of FIG. 1 operates as follows. If the processor 114 of the host computer 102 issues a read command to the disk array controller 106 and if the information requested is in the cache 126, the I/O management controller 124 forwards the requested information to the processor 114 and a disk access is not necessary. To reiterate, this is known as a "cache hit". If, on the other hand, the information requested is not in the cache 126, the I/O management controller 124 retrieves the requested information from the disk array 106 and forwards it to both the cache 126 and the processor 114. To reiterate, this is known as a "cache miss".
.sctn.1.1 The Purpose of Cache Flushing and Replacement Algorithms
A cache, in its entirety, may be flushed (a) periodically, or (b) when certain predefined conditions are met. Further, individual cache lines may be flushed as part of a replacement algorithm. In each case, dirty data (i.e., data not yet written to persistent memory) in the cache to be flushed or in the cache line to be flushed is written to persistent memory. Dirty bits, which identify blocks of a cache line containing dirty data, are then cleared. The flushed cache or flushed cache lines can then store new blocks of data.
FIG. 4 is a flow diagram of a cache flush process 400. As shown in steps 402 and 404, if a cache flush is scheduled or if predetermined conditions for a cache flush are met, the cache is flushed. That is, all dirty data in the cache is written to the persistent memory. The entire cache is now available to store new blocks of data. In some known cache flushing methods, discussed below, the cache is flushed just before system shutdown.
Further, as shown in steps 406 and 408, if the cache is full when a cache line is requested, a cache line is selected (e.g., based on a replacement algorithm) and the selected cache line is flushed. The flushed cache line is now available to store new blocks of data.
.sctn.1.2 Known Cache Flushing Techniques
.sctn.1.2.1 Replacement Algorithm and Full Flush at Shutdown and its Problems
Known systems use a replacement algorithm to flush cache line(s) when a cache line is needed. Such systems may further perform a full cache flush just before system shutdown. Such systems are inefficient and expose write-back data (i.e., data written to cache to be written to persistent memory at a later time--thus, write-back data is dirty data) to loss. More specifically, with respect to the inefficiency of such systems, if a dirty cache line must be replaced to permit an I/O request to be processed, the I/O request must wait for the dirty data to be written to persistent memory before it can continue. This inefficiency caused by placing the bulk of the cache flushing burden on the replacement algorithm can become acute in instances where most of the I/O requests are random writes (i.e., writes to non-sequential storage locations). With respect to the potential loss of data, if write-back data kept in the cache (i.e., dirty data) is not flushed until the system shutdown or until the replacement algorithm determines it is the cache line to be replaced, it is kept in the cache for a prolonged time period, during which it is subject to loss, before it is written to persistent memory.
.sctn.1.2.2 Flush upon CPU Idle and its Problems
Other known systems flush the cache when a central processing unit (or "CPU") idle condition is detected, in addition to flushing subject to a replacement algorithm and/or subject to system shutdown as discussed above. While dirty data in these systems is less likely to be lost, using CPU idle as the only factor for determining when to flush a cache also has disadvantages. First, it is possible for the data bus to be overloaded when the CPU is idle. This circumstance is especially a concern in systems employing one or more direct memory access (or "DMA") units because DMA units exchange data with memory exclusive of the CPU. Flushing the cache during a DMA would disadvantageously further burden an already crowded data bus. In addition, although the frequency of flushing cache lines by a replacement algorithm is reduced as compared with the systems in which cache lines are flushed only by the replacement algorithm, the burden of cache line flushing on the replacement algorithm is still relatively high.
In view of the above drawbacks of known cache flushing methods, an improved flushing method is needed. The improved flushing method should minimize the frequency of cache line flushes initiated by a replacement algorithm so that I/O requests do not have to wait for data in the cache to be written to mass storage.